An especially beneficial application of such a memory circuit relates to devising a database for an Aho-Corasick type final state deterministic character recognition automaton for recognizing multiple information or MPR, also known by the term multi-pattern recognition. For example, but not exclusively, the recognition of characters may be used in the field of computing to recognize signatures of computer viruses in intrusion detection systems in which known attack signatures are detected.
Referring to FIG. 1, a character recognition automaton MPR is therefore based on the use of a database B in which is stored a list of words, or in a general manner, a list of character strings or patterns to be recognized in an incoming file F. The patterns are stored in the database B in the form of a node tree in which each node corresponds to a state of the automaton and to a recognition of a sequence of characters of a pattern to be recognized.
The structure and the devising of an Aho-Corasick type automaton are well known to those skilled in the art, and are therefore not described in detail below. In this regard, reference is made to the article “A. Aho and M. Corasick: Efficient String Machine, An Aid To Bibliographic Search, in Communications of the ACM”, 18 (6): 333-340, 1975.
The construction of an Aho-Corasick automaton first requires the devising of the database B by providing, for each pattern M to be recognized, the states and the direct transitions which lead to the recognition of the pattern. In particular, with each state is associated a transition vector which serves to determine the destination node or nodes of a transition.
To do this, with each state is associated transition parameters for calculating with a transition function the states accessible from each node. Devising the database is a very complex step to implement and requires relatively significant amounts of hardware, particularly in terms of memory. Thus, in an application for searching for computer virus signatures, the size of the memory required to implement an Aho-Corasick type automaton may attain, or even exceed, 100 MB,